package offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/2/19
 **/
@FunctionalInterface
public interface PancakeSort {
    /**
     *给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
     *
     * 一次煎饼翻转的执行过程如下：
     *
     * 选择一个整数 k ，1 <= k <= arr.length
     * 反转子数组 arr[0...k-1]（下标从 0 开始）
     * 例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
     *
     * 以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。
     *
     * @param arr
     * @return
     */
    List<Integer> pancakeSort(int[] arr);
}
class PancakeSortImpl1 implements PancakeSort{

    static int[] TEST_01 = new int[]{3,2,4,1};

    public static void main(String[] args) {
        new PancakeSortImpl1().pancakeSort(TEST_01);
        for(int num : TEST_01){
            System.out.print(num +",");
        }
    }

    /**
     * 一次兼并排序需要o(n)的时间，题目说可接受10*n次数以内的煎饼排序，即o(n^2)时间，所以选择排序
     * @param arr
     * @return
     */
    @Override
    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        if(n == 1 || n == 0){
            return new ArrayList<>();
        }else if(n == 2){
            if(arr[0] > arr[1]){
                return new ArrayList<>();
            }else{
                List<Integer> ans = new ArrayList<>();
                ans.add(2);
                return ans;
            }
        }

        List<Integer> ans = new ArrayList<>();
        // 选择排序走一波
        for (int i = 0; i < n - 1; i++) {
            int max = arr[0];
            int maxIndex = 0;
            // o(n)找到最大值
            for (int j = n - i - 1; j >= 0; j--) {
                if(arr[j] > max){
                    maxIndex = j;
                    max = arr[j];
                }
            }
            if(maxIndex == n - i - 1){
                // 不交换
            }else if(maxIndex == 0){
                ans.add(n - i);
                reverse(arr, n - i);
            }else{
                ans.add(maxIndex + 1);
                ans.add(n - i + 1);
                reverse(arr, maxIndex + 1);
                reverse(arr, n - i);
            }
        }
        return ans;
    }
    private void reverse(int[] nums, int k){
        int left = 0, right = k - 1;
        while(left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
